package greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author wcj
 * @Date 2021/7/6 22:21
 * @Version 1.0
 */
public class Region {

    /**
     * 使得区间互相不重叠，所需要移除的最少的区间个数，[1,2][2,3]不算重叠
     * ①贪心策略：怎么使得区间能不重叠呢？其实就是需要当前区间足够小，这样留给其它区间的空间就足够大
     *
     * @param arr
     * @return
     */
    public static int greed(int[][] arr) {
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int count = 1;
        int pre = arr[0][1];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i][0] >= pre) {
                pre = arr[i][1];
                count++;
            }
        }
        return arr.length - count;
    }
}
